package shuzu

import (
	"math"
	"sort"
)

func MinSubArray(target int, nums []int) int {
	// 蠢方法，会超时
	ans := math.MaxInt32
	for i := 0; i < len(nums); i++ {
		total := 0
		times := 0
		for j := i; j < len(nums); j++ {
			total += nums[j]
			times++
			if total >= target && times < ans {
				ans = times
			}
		}
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

// 滑动窗口

func MinSubArray2(target int, nums []int) int {
	front, end, total, ans := 0, 0, 0, math.MaxInt32
	for end < len(nums) {
		total += nums[end]
		for total >= target {
			total -= nums[front]
			if total < target {
				if ans > end-front+1 {
					ans = end - front + 1
				}
			}
			front++
		}
		end++
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

// 二分法

func MinSubArray3(s int, nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	ans := math.MaxInt32
	sums := make([]int, n+1)
	// 为了方便计算，令 size = n + 1
	// sums[0] = 0 意味着前 0 个元素的前缀和为 0
	// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
	// 以此类推
	for i := 1; i <= n; i++ {
		sums[i] = sums[i-1] + nums[i-1]
	}
	for i := 1; i <= n; i++ {
		target := s + sums[i-1]
		bound := sort.SearchInts(sums, target)
		if bound < 0 {
			bound = -bound - 1
		}
		if bound <= n {
			ans = min(ans, bound-(i-1))
		}
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
